package com.SuanFa.jiangdongqi;

import java.util.ArrayList;
import java.util.List;

class aa {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        boolean[] used = new boolean[nums.length]; // 标记数字是否被使用
        List<Integer> path = new ArrayList<>();    // 当前路径

        backtrack(nums, used, path, res);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        // 终止条件：当前路径长度等于 nums 的长度，说明找到一个排列
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); // 注意：要 new 一个新的 ArrayList，否则后续修改会影响结果
            return;
        }

        // 遍历所有数字，尝试选择未被使用的数字
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) { // 如果数字未被使用
                used[i] = true;          // 标记为已使用
                path.add(nums[i]);       // 加入当前路径

                backtrack(nums, used, path, res); // 递归继续选择下一个数字

                // 回溯：撤销选择，尝试其他可能性
                path.remove(path.size() - 1); // 移除最后一个数字
                used[i] = false;            // 标记为未使用
            }
        }
    }
}

